package top.lshaci.learning.algorithm;

import cn.hutool.core.collection.CollUtil;

import java.util.*;

/**
 * BinaryTree
 * <p>
 * 二叉树
 *
 * @author liangxu
 */
public class BinaryTree {

    /**
     * 构建二叉树
     *
     * @param inputList 输入序列
     * @return 二叉树节点
     */
    public static TreeNode createBinaryTree(LinkedList<Integer> inputList) {
        if (CollUtil.isEmpty(inputList)) {
            return null;
        }
        Integer data = inputList.removeFirst();
        if (data == null) {
            return null;
        }
        TreeNode node = new TreeNode(data);
        node.leftChild = createBinaryTree(inputList);
        node.rightChild = createBinaryTree(inputList);
        return node;
    }

    /**
     * 二叉树前序遍历
     *
     * @param node 二叉树节点
     */
    public static void preOrderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }
        System.err.println(node.data);
        preOrderTraversal(node.leftChild);
        preOrderTraversal(node.rightChild);
    }

    /**
     * 二叉树中序遍历
     *
     * @param node 二叉树节点
     */
    public static void inOrderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }
        inOrderTraversal(node.leftChild);
        System.err.println(node.data);
        inOrderTraversal(node.rightChild);
    }

    /**
     * 二叉树后序遍历
     *
     * @param node 二叉树节点
     */
    public static void postOrderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }
        postOrderTraversal(node.leftChild);
        postOrderTraversal(node.rightChild);
        System.err.println(node.data);
    }

    /**
     * 二叉树非递归前序遍历
     *
     * @param root 二叉树根节点
     */
    public static void preOrderTraversalWithStack(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode treeNode = root;
        while (treeNode != null || !stack.isEmpty()) {
            // 迭代访问节点在左孩子, 并入栈
            while (treeNode != null) {
                System.err.println(treeNode.data);
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }
            // 如果节点没有左孩子, 则弹出栈顶节点, 访问节点右孩子
            if (!stack.isEmpty()) {
                treeNode = stack.pop();
                treeNode = treeNode.rightChild;
            }
        }
    }

    /**
     * 二叉树非递归中序遍历
     *
     * @param root 二叉树根节点
     */
    public static void inOrderTraversalWithStack(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode treeNode = root;
        while (treeNode != null || !stack.isEmpty()) {
            // 迭代访问左节点, 并入栈
            while (treeNode != null) {
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }
            // 如果节点没有左孩子, 则弹出栈顶节点, 访问节点右孩子
            if (!stack.isEmpty()) {
                treeNode = stack.pop();
                System.err.println(treeNode.data);
                treeNode = treeNode.rightChild;
            }
        }
    }

    /**
     * 二叉树非递归后序遍历
     *
     * @param root 二叉树根节点
     */
    public static void postOrderTraversalWithStack(TreeNode root) {
        Stack<TreeNode> temp = new Stack<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode treeNode = root;
        while (treeNode != null || !temp.isEmpty()) {
            // 迭代访问右节点, 并入栈
            while (treeNode != null) {
                temp.push(treeNode);
                stack.push(treeNode);
                treeNode = treeNode.rightChild;
            }
            if (!stack.isEmpty()) {
                // 节点弹出栈
                treeNode = temp.pop();
                // 转向左子树
                treeNode = treeNode.leftChild;
            }
        }
        while (!stack.isEmpty()) {
            treeNode = stack.pop();
            System.err.println(treeNode.data);
        }
    }

    /**
     * 二叉树层序遍历
     *
     * @param root 二叉树根节点
     */
    public static void levelOrderTraversal(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.err.println(node.data);
            Optional.ofNullable(node.leftChild).ifPresent(queue::offer);
            Optional.ofNullable(node.rightChild).ifPresent(queue::offer);
        }
    }

    /**
     * 二叉树节点
     */
    private static class TreeNode {
        int data;
        TreeNode leftChild;
        TreeNode rightChild;

        TreeNode(int data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return "{" +
                    "root=" + data +
                    ", leftChild=" + (leftChild == null ? null : leftChild.data) +
                    ", rightChild=" + (rightChild == null ? null : rightChild.data) +
                    '}';
        }
    }

    public static void main(String[] args) {
        LinkedList<Integer> inputList = new LinkedList<>(Arrays.asList(3, 2, 9, null, null, 10, null, null, 8, null, 4));
        //      3
        //   2    8
        // 9  10    4
        TreeNode treeNode = createBinaryTree(inputList);
        System.err.println("前序遍历: ");
        preOrderTraversal(treeNode);
        System.err.println("中序遍历: ");
        inOrderTraversal(treeNode);
        System.err.println("后序遍历: ");
        postOrderTraversal(treeNode);
        System.err.println("前序遍历（非递归）: ");
        preOrderTraversalWithStack(treeNode);
        System.err.println("中序遍历（非递归）: ");
        inOrderTraversalWithStack(treeNode);
        System.err.println("后序遍历（非递归）: ");
        postOrderTraversalWithStack(treeNode);
        System.err.println("层序遍历: ");
        levelOrderTraversal(treeNode);
    }
}

